package chapter2;

import java.util.Arrays;

public class MergeSort {
    public static void process(int[] arr,int L,int R){
        if (L==R){
            return;
        }
        int mid = L + (R-L>>1);//>>的优先级低于加减运算
        process(arr,L,mid);
        process(arr,mid+1,R);
        merge(arr,L,mid,R);
    }
    public static void merge(int[] arr,int L,int mid,int R){
        int[] help = new int[R-L+1];
        int i =0;
        int leftPoint = L;
        int rightPoint = mid+1;
        while (leftPoint<=mid && rightPoint <= R){
            help[i++] = arr[leftPoint] < arr[rightPoint]?arr[leftPoint++]:arr[rightPoint++];
        }
        while (leftPoint <= mid){
            help[i++] = arr[leftPoint++];
        }
        while (rightPoint <= R){
            help[i++] = arr[rightPoint++];
        }
        for (int j = 0; j <= R-L; j++) {
            arr[L+j] = help[j];
        }
    }


    public static void main(String[] args) {
        int[] arr= {4,58,6,55};
        process(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}
